/**
 * 617. 合并二叉树
 * https://leetcode-cn.com/problems/merge-two-binary-trees/
 */
public class Solutions_617 {
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        t1.left = new TreeNode(3);
        t1.left.left = new TreeNode(5);
        t1.right = new TreeNode(2);

        TreeNode t2 = new TreeNode(2);
        t2.left = new TreeNode(1);
        t2.left.right = new TreeNode(4);
        t2.right = new TreeNode(3);
        t2.right.right = new TreeNode(7);  // output: {3, 4, 5, 5, 4, null, 7}

        TreeNode result = mergeTrees(t1, t2);
        System.out.println(result);
    }

    public static TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t2 == null) {
            // 返回 t1 的树结构
            return t1;
        }
//        if (t1 == null && t2 != null) {
        if (t1 == null) {
            // 返回 t2 的树结构
            return t2;
        }
        // 累加节点值
        t1.val += t2.val;
        // 同时递归 t1 与 t2 的子树，将返回的树作为 t1 新的子树
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }
}
